package hot;

/**
 * @author lakersUp
 * @Classname   寻找两个正序数组的中位数
 * @Description  时间复杂度限制log(m+n), 二分寻找第k个数
 *              k=(M+N+1)/2, 分别二分寻找第k/2个数
 *              对K二分，意思是我们需要分别在nums1和nums2中查找第K/2个元素
 * @Date 2022/3/7 11:06
 * @Version 1.0
 */
public class Hot4findMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m=nums1.length;
        int n=nums2.length;
        int kl=(m+n+1)/2;
        int kr=(m+n+2)/2;
        return (findKth(nums1,0,nums2,0,kl)+findKth(nums1,0,nums2,0,kr))/2;
    }

    private double findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if(i>=nums1.length){
            return nums2[j+k-1];
        }
        if(j>=nums2.length){
            return nums1[i+k-1];
        }
        if(k==1){
            return Math.min(nums1[i],nums2[j]);
        }
        int midval1=(i+k/2-1)>nums1.length?Integer.MAX_VALUE:nums1[i+k/2-1];
        int midval2=(j+k/2-1)>nums2.length?Integer.MAX_VALUE:nums2[j+k/2-1];
        //如果第一个数组的第K/2个数字小的话，那么说明我们要找的数字肯定不在nums1中的前K/2个数字，
        if(midval1<midval2){
            return findKth(nums1, i+k/2, nums2, j, k-k/2);
        }else {
            return findKth(nums1, i, nums2, j+k/2, k-k/2);
        }
    }
}
